package cyc2018.二分查找.原理;

/**
 * 有序数组中的单一元素
 */
public class Test540 {


    // 方法一
    public static int singleNonDuplicate(int[] nums) {
        int i = 0;
        for (; i < nums.length; i += 2) {
            if (i + 2 < nums.length && nums[i] != nums[i+1] && nums[i + 1] == nums[i + 2]) {
                return nums[i];
            }
            if (i == nums.length - 1) {
                return nums[i];
            }
        }
        return -1;
    }

    // 方法二
    public static int singleNonDuplicate2(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            // 确保 start、end、mid在偶数位上
            if ((mid & 1) == 1) {
                mid--;
            }
            if (nums[mid] == nums[mid + 1]) {
                // single 数字在 mid + 1 右边
                start = mid + 2;
            } else {
                // single 数字在 mid+ 1 左边
                end = mid;
            }
        }
        return nums[start];
    }

    public static void main(String[] args) {
//        int[] nums = {1,1,2,3,3,4,4,8,8};
//        int[] nums = {3,3,7,7,10,11,11};
        int[] nums = {1,1,2};
        System.out.println(singleNonDuplicate2(nums));
    }
}
